home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / BOOL1LOW.C < prev    next >
C/C++ Source or Header  |  1991-12-15  |  32KB  |  875 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see Irit.h)!             *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersection polyline between the oper.    *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. * Note we said mainly has routines CAN call one another!             *
  18. *****************************************************************************/
  19.  
  20. /* #define DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #ifdef __MSDOS__
  24. #include <alloc.h>
  25. #include <dos.h>
  26. #endif /* __MSDOS__ */
  27.  
  28. #include <stdio.h>
  29. #include <ctype.h>
  30. #include <math.h>
  31. #include <string.h>
  32. #include "program.h"
  33. #include "adjacncy.h"
  34. #include "allocate.h"
  35. #include "booleang.h"
  36. #include "booleanl.h"
  37. #include "geomat3d.h"
  38. #include "objects.h"
  39.  
  40. static int ObjectsIntersect;
  41.  
  42. static ObjectStruct *BooleanLowGenInOut(ObjectStruct *PObj1, int InOut);
  43. static void BooleanLowInterAll(ObjectStruct *PObj1, ObjectStruct *PObj2);
  44. static void BooleanLowInterOne(PolygonStruct *Pl1, PolygonStruct *Pl2);
  45. static InterSegmentStruct *InterSegmentPoly(PolygonStruct *Pl,
  46.                 PolygonStruct *SegPl, PointType Segment[2]);
  47. static void SwapPointInterList(InterSegmentStruct *PSeg);
  48. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  49.                         InterSegmentStruct **PSegList);
  50. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  51.                         InterSegmentStruct **PSegList);
  52. static void SortOpenReverseLoop(SortOpenStruct *PSHead);
  53. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  54.        SortOpenStruct *PSTemp, PointType Pt, VertexStruct *V, PolygonStruct *Pl);
  55. static ObjectStruct *PolylineFromInterSeg(ObjectStruct *PObj);
  56.  
  57. #ifdef DEBUG2
  58. static void PrintVrtxList(VertexStruct *V);
  59. static void PrintInterList(InterSegmentStruct *PInt);
  60. #endif /* DEBUG2 */
  61.  
  62. /*****************************************************************************
  63. *   Routine to find the part of PObj1 which is out of PObj2:             *
  64. *****************************************************************************/
  65. ObjectStruct *BooleanLow1Out2(ObjectStruct *PObj1, ObjectStruct *PObj2)
  66. {
  67. #ifdef DEBUG3
  68.     printf("Enter BooleanLow1Out2\n");
  69. #endif /* DEBUG3 */
  70.  
  71.     GenAdjacencies(PObj1);
  72.  
  73.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  74.     ObjectsIntersect = FALSE;
  75.     BooleanLowInterAll(PObj1, PObj2);
  76.  
  77.     /* Generate all the polygons in PObj1 which are out of PObj2. */
  78.     if (!ObjectsIntersect) {
  79.     FatalBooleanError(FTL_BOOL_NO_INTER);
  80.     }
  81.     return BooleanLowGenInOut(PObj1, FALSE);
  82. }
  83.  
  84. /*****************************************************************************
  85. *   Routine to find the part of PObj1 which is in PObj2:             *
  86. *****************************************************************************/
  87. ObjectStruct *BooleanLow1In2(ObjectStruct *PObj1, ObjectStruct *PObj2)
  88. {
  89. #ifdef DEBUG3
  90.     printf("Enter BooleanLow1In2\n");
  91. #endif /* DEBUG3 */
  92.  
  93.     GenAdjacencies(PObj1);
  94.  
  95.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  96.     ObjectsIntersect = FALSE;
  97.     BooleanLowInterAll(PObj1, PObj2);
  98.  
  99.     /* Generate all the polygons in PObj1 which are in PObj2. */
  100.     if (!ObjectsIntersect) {
  101.     FatalBooleanError(FTL_BOOL_NO_INTER);
  102.     }
  103.     return BooleanLowGenInOut(PObj1, TRUE);
  104. }
  105.  
  106. /*****************************************************************************
  107. *   Scan the InterSegmentList of each polygon and decide using Intersection  *
  108. * list, if it is IN relative to the other object. Note that for polygons     *
  109. * that does not intersect at all, we use the polygon adjacencies to decide   *
  110. * if they are IN or not.                             *
  111. *****************************************************************************/
  112. static ObjectStruct *BooleanLowGenInOut(ObjectStruct *PObj, int InOut)
  113. {
  114.     if (BooleanOutputInterCurve) {
  115.     /* Return a polyline object - extract the InterSegment list of each  */
  116.     /* polygon into open/closed polyline loops object.             */
  117.     return PolylineFromInterSeg(PObj);
  118.     }
  119.     else
  120.     return ExtractPolygons(PObj, InOut);
  121. }
  122.  
  123. /*****************************************************************************
  124. *   Create a polyline object out of the intersection list of the polygons.   *
  125. *****************************************************************************/
  126. static ObjectStruct *PolylineFromInterSeg(ObjectStruct *PObj)
  127. {
  128.     ObjectStruct *PObjRet;
  129.     PolygonStruct *PlTemp, *PlHead = NULL, *PlObj;
  130.     InterSegmentStruct *PInter, *PInterNext;
  131.     InterSegListStruct *PClosed, *POpen, *PClosedNext, *POpenNext;
  132.     VertexStruct *V;
  133.  
  134.     PlObj = PObj -> U.Pl.P;
  135.     while (PlObj != NULL) {
  136.     LoopsFromInterList(PlObj, &PClosed, &POpen);
  137.     while (POpen != NULL) {
  138.         /* Make one polyline from each loop in list: */
  139.         PInter = POpen -> PISeg;
  140.         POpenNext = POpen -> Pnext;
  141.  
  142.         PlTemp = AllocPolygon(0, 0, NULL, NULL);
  143.         PlTemp -> V = V = AllocVertex(0, 0, NULL, NULL);
  144.         PT_COPY(V -> Pt, PInter -> PtSeg[0]);
  145.         while (PInter) {
  146.         PInterNext = PInter -> Pnext;
  147.  
  148.         V -> Pnext = AllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  149.         PT_COPY(V -> Pt, PInter -> PtSeg[1]);
  150.  
  151.         MyFree((char *) PInter, ALLOC_OTHER);
  152.         PInter = PInterNext;
  153.         }
  154.         PlTemp -> Pnext = PlHead;
  155.         PlHead = PlTemp;
  156.  
  157.         MyFree((char *) POpen, ALLOC_OTHER);
  158.         POpen = POpenNext;
  159.     }
  160.     while (PClosed != NULL) {
  161.         /* Make one polyline from each loop in list: */
  162.         PInter = PClosed -> PISeg;
  163.         PClosedNext = PClosed -> Pnext;
  164.  
  165.         PlTemp = AllocPolygon(0, 0, NULL, NULL);
  166.         PlTemp -> V = V = AllocVertex(0, 0, NULL, NULL);
  167.         PT_COPY(V -> Pt, PInter -> PtSeg[0]);
  168.         while (PInter) {
  169.         V -> Pnext = AllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  170.         PT_COPY(V -> Pt, PInter -> PtSeg[1]);
  171.         PInter = PInter -> Pnext;
  172.         }
  173.         PlTemp -> Pnext = PlHead;
  174.         PlHead = PlTemp;
  175.  
  176.         MyFree((char *) PClosed, ALLOC_OTHER);
  177.         PClosed = PClosedNext;
  178.     }
  179.     PlObj = PlObj -> Pnext;
  180.     }
  181.  
  182.     PObjRet = GenPolyObject("", PlHead, NULL);
  183.     SET_POLYLINE_OBJ(PObjRet);              /* Mark it as polyline object. */
  184.     return PObjRet;
  185. }
  186.  
  187. /*****************************************************************************
  188. *   Routine to find all the intersections between all PObj1 polygons with    *
  189. * PObj2 polygons. The intersections are saved as a list of segments (struct  *
  190. * InterSegmentStruct) in each of PObj1 polygons using the PAux pointer (see  *
  191. * PolygonStruct). Note PObj2 is not modified at all, and in PObj1, only PAux *
  192. * of each polygon is set to the segment list, or NULL if none             *
  193. *****************************************************************************/
  194. static void BooleanLowInterAll(ObjectStruct *PObj1, ObjectStruct *PObj2)
  195. {
  196.     PolygonStruct *Pl1, *Pl2;
  197.  
  198. #ifdef DEBUG3
  199.     printf("Enter BooleanLowInterAll\n");
  200. #endif /* DEBUG3 */
  201.  
  202.     Pl1 = PObj1 -> U.Pl.P;
  203.     while (Pl1 != NULL) {
  204.     Pl1 -> PAux = NULL;       /* Empty InterSegment list to start with: */
  205.  
  206.     Pl2 = PObj2 -> U.Pl.P;
  207.     while (Pl2 != NULL) {
  208.         BooleanLowInterOne(Pl1, Pl2);
  209.         Pl2 = Pl2 -> Pnext;
  210.     }
  211.     ObjectsIntersect |= (Pl1 -> PAux != NULL);   /* If any intersection. */
  212.  
  213.     Pl1 = Pl1 -> Pnext;
  214.     }
  215.  
  216. #ifdef DEBUG3
  217.     printf("Exit BooleanLowInterAll\n");
  218. #endif /* DEBUG3 */
  219. }
  220.  
  221. /*****************************************************************************
  222. *   Routine to intersect polygon Pl1, with polygon Pl2. If found common      *
  223. * intersection, that segment will be added to the InterSegmentStruct list    *
  224. * saved in Pl1 PAux list.                             *
  225. *   Note that as the two polygons convex, only one segment can result from   *
  226. * such intersection.                                 *
  227. *   Algorithm: intersect all Pl2 edges with Pl1 plane. If found that         *
  228. * (exactly) two vertices (one segment) of Pl2 do intersect Pl1 plane then:   *
  229. * Perform clipping of the segment against Pl1. If result is not empty, add   *
  230. * the result segment to Pl1 InterSegmentStruct list (saved at PAux of         *
  231. * polygon - see PolygonStruct).                             *
  232. *****************************************************************************/
  233. static void BooleanLowInterOne(PolygonStruct *Pl1, PolygonStruct *Pl2)
  234. {
  235.     int NumOfInter = 0;
  236.     RealType TInter[2],
  237.     *Plane = Pl1 -> Plane;                   /* For faster access. */
  238.     PointType Inter[2], Dir;
  239.     VertexStruct *Vnext, *V = Pl2 -> V;
  240.     InterSegmentStruct *PSeg, *PLSeg;
  241.  
  242. #ifdef DEBUG3
  243.     printf("Enter BooleanLowInterOne\n");
  244. #endif /* DEBUG3 */
  245.  
  246.     TestBooleanCtrlBrk();
  247.  
  248.     do {
  249.     Vnext = V -> Pnext;
  250.     PT_SUB(Dir, Vnext -> Pt, V -> Pt);
  251.     if (CGPointFromLinePlane01(V -> Pt, Dir, Plane, Inter[NumOfInter],
  252.                             &TInter[NumOfInter]) &&
  253.         ((NumOfInter == 0) || (NumOfInter == 1 &&
  254.                    !PT_EQ(Inter[0], Inter[1]))))
  255.         NumOfInter++;
  256.     if (NumOfInter == 2) break;       /* Cannt have more intersections. */
  257.  
  258.     V = Vnext;
  259.     }
  260.     while (V != NULL && V != Pl2 -> V);
  261.  
  262.     switch (NumOfInter) {
  263.     case 0:
  264.         break;
  265.     case 1:
  266.         /* One intersection is possible if only one vertex of Pl2 is in  */
  267.         /* the plane of Pl1, all other vertices are on one side of plane.*/
  268.         break;
  269.     case 2:
  270.         /* Clip the segment against the polygon and insert if not empty: */
  271.         if ((PSeg = InterSegmentPoly(Pl1, Pl2, Inter)) != NULL) {
  272.         /* insert that segment to list of Pl1. Note however that the */
  273.         /* intersection may be exactly on 2 other polygons boundary, */
  274.         /* And therefore creates the same intersection edge TWICE!   */
  275.         /* Another possiblity is on same case, the other polygon     */
  276.         /* will have that inter. edge on its edge, and its ignored.  */
  277.         /* We therefore test for duplicates and ignore edge if so    */
  278.         if (PSeg -> V[0] != NULL && PSeg -> V[0] == PSeg -> V[1]) {
  279.             MyFree((char *) PSeg, ALLOC_OTHER);           /* Ignore it! */
  280.             return;
  281.         }
  282.         PLSeg = (InterSegmentStruct *) Pl1 -> PAux;
  283.         while (PLSeg != NULL) {
  284.             if ((PT_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[0]) &&
  285.              PT_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[1])) ||
  286.             (PT_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[1]) &&
  287.              PT_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[0]))) {
  288.             MyFree((char *) PSeg, ALLOC_OTHER);     /* Ignore it! */
  289.             return;
  290.             }
  291.             PLSeg = PLSeg -> Pnext;
  292.         }
  293.  
  294.         PSeg -> Pnext = (InterSegmentStruct *) Pl1 -> PAux;
  295.         Pl1 -> PAux = (VoidPtr) PSeg;
  296.         }
  297.         break;
  298.     }
  299.  
  300. #ifdef DEBUG3
  301.     printf("Exit BooleanLowInterOne\n");
  302. #endif /* DEBUG3 */
  303. }
  304.  
  305. /*****************************************************************************
  306. *   Intersects the given segment (given as two end points), with the given   *
  307. * polygon (which must be convex). Upto two intersections are possible, as    *
  308. * again, the polygon is convex. Note Segment polygon is given as SegPl.      *
  309. *****************************************************************************/
  310. static InterSegmentStruct *InterSegmentPoly(PolygonStruct *Pl,
  311.                 PolygonStruct *SegPl, PointType Segment[2])
  312. {
  313.     int i, NumOfInter = 0, Reverse, Res;
  314.     RealType TInter[2], temp, Min, Max, *PtSeg0, *PtSeg1;
  315.     PointType Dir, Inter[2], SegDir, Pt1, Pt2;
  316.     VertexStruct *VInter[2], *V = Pl -> V, *Vnext;
  317.     InterSegmentStruct *PSeg;
  318.  
  319.     /* Find the segment direction vector: */
  320.     PT_SUB(SegDir, Segment[1], Segment[0]);
  321.  
  322. #ifdef DEBUG3
  323.     printf("Enter InterSegmentPoly\n");
  324. #endif /* DEBUG3 */
  325.  
  326.     do {
  327.     Vnext = V -> Pnext;
  328.     PT_SUB(Dir, Vnext -> Pt, V -> Pt);
  329.     /* Find the intersection of the segment with all the polygon edges: */
  330.     /* Note the t parameter value of the edge (temp) must be in [0..1]. */
  331.     if ((Res = CG2PointsFromLineLine(Segment[0], SegDir,
  332.         V -> Pt, Dir, Pt1, &TInter[NumOfInter], Pt2, &temp)) != 0 &&
  333.         (temp > 0.0 || APX_EQ(temp, 0.0)) &&
  334.         (temp < 1.0 || APX_EQ(temp, 1.0)) && PT_EQ(Pt1, Pt2) &&
  335.         (NumOfInter == 0 ||
  336.          (NumOfInter == 1 && !APX_EQ(TInter[0], TInter[1])))) {
  337.         PT_COPY(Inter[NumOfInter], Pt1);
  338.         VInter[NumOfInter++] = V;   /* Save pointer to intersected edge. */
  339.     }
  340.     else {
  341.         /* If Res == 0 its parallel to edge. If distance is zero then    */
  342.         /* line is on the edge line itself - quit from this one!         */
  343.         if (!Res && CGDistPointPoint(Pt1, Pt2) < EPSILON) {
  344.         /* Wipe out adjacency of this vertex as we dont want to      */
  345.         /* propagate through this one nothing - its on in/out border.*/
  346.         VertexStruct *Vtemp;
  347.  
  348.         if (V -> PAdj == NULL) return NULL;
  349.  
  350.         Vtemp = V -> PAdj -> V;
  351.         do {/* Find the edge on the other polygon to wipe out first. */
  352.             if (Vtemp -> PAdj == Pl) {
  353.             Vtemp -> PAdj = NULL;
  354.             break;
  355.             }
  356.             Vtemp = Vtemp -> Pnext;
  357.         }
  358.         while (Vtemp != NULL && Vtemp != V -> PAdj -> V);
  359.         V -> PAdj = NULL;        /* And wipe out ours also... */
  360.         return NULL;
  361.         }
  362.     }
  363.  
  364.     V = Vnext;
  365.     }
  366.     while (V != NULL && V != Pl -> V && NumOfInter < 2);
  367.  
  368.     switch (NumOfInter) {
  369.     case 0:
  370.         return NULL;
  371.     case 1:
  372.         /* One intersection is possible if segment intersects one vertex */
  373.         /* of polygon and all other vertices are on same side of segment.*/
  374.         return NULL;
  375.     case 2:
  376.         /* In order the segment to really intersect the polygon, it must */
  377.         /* at list part of t in [0..1] in the polygon. Test it:         */
  378.         Min = MIN(TInter[0], TInter[1]);
  379.         Max = MAX(TInter[0], TInter[1]);
  380.         Reverse = TInter[0] > TInter[1];
  381.         if (Min >= 1.0 || APX_EQ(Min, 1.0) ||
  382.         Max <= 0.0 || APX_EQ(Max, 0.0)) return NULL;
  383.  
  384.         PSeg = (InterSegmentStruct *) MyMalloc(sizeof(InterSegmentStruct),
  385.                                 ALLOC_OTHER);
  386.         PSeg -> Pl = SegPl;     /* Pointer to other (intersect) polygon. */
  387.  
  388.         /* Handle the Min end point: */
  389.         if (APX_EQ(Min, 0.0)) {
  390.         PtSeg0 = Segment[0];
  391.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  392.         }
  393.         else if (Min < 0.0) {
  394.         PtSeg0 = Segment[0];
  395.         PSeg -> V[0] = NULL;             /* End is internal. */
  396.         }
  397.         else { /* Min > 0.0 */
  398.         PtSeg0 = (Reverse ? Inter[1] : Inter[0]);
  399.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  400.         }
  401.  
  402.         /* Handle the Max end point: */
  403.         if (APX_EQ(Max, 1.0)) {
  404.         PtSeg1 = Segment[1];
  405.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  406.         }
  407.         else if (Max > 1.0) {
  408.         PtSeg1 = Segment[1];
  409.         PSeg -> V[1] = NULL;             /* End is internal. */
  410.         }
  411.         else { /* Max < 1.0 */
  412.         PtSeg1 = (Reverse ? Inter[0] : Inter[1]);
  413.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  414.         }
  415.  
  416.         PT_COPY(PSeg -> PtSeg[0], PtSeg0); /* The two segment end point. */
  417.             PT_COPY(PSeg -> PtSeg[1], PtSeg1);
  418.  
  419.         for (i = 0; i < 3; i++) {         /* Make zeros look nicer... */
  420.         if (ABS(PSeg -> PtSeg[0][i]) < EPSILON)
  421.             PSeg -> PtSeg[0][i] = 0.0;
  422.         if (ABS(PSeg -> PtSeg[1][i]) < EPSILON)
  423.             PSeg -> PtSeg[1][i] = 0.0;
  424.         }
  425.         if (PT_EQ(PSeg -> PtSeg[0], PSeg -> PtSeg[1])) {
  426.         MyFree((char *) PSeg, ALLOC_OTHER);
  427.         return NULL;
  428.         }
  429.         return PSeg;
  430.     }
  431.     return NULL;                    /* Makes warning silent. */
  432. }
  433.  
  434. /*****************************************************************************
  435. *   Given a polygon with the intersection list, create the polylines loop(s) *
  436. * out of it, which can be one of the two:                     *
  437. * 1. Closed loop - all the intersection create a loop in one polygon.         *
  438. * 2. Open polyline - if the intersection crosses the polygon boundary. In    *
  439. *    this case the two end point of the polyline, must lay on polygon         *
  440. *    boundary.                                     *
  441. * In both cases, the polyline will be as follows:                 *
  442. * First point at first list element at PtSeg[0] (see InterSegmentStruct).    *
  443. * Second point at first list element at PtSeg[1] (see InterSegmentStruct).   *
  444. * Point i at list element (i-1) at PtSeg[0] (PtSeg[1] is not used!).         *
  445. * In the closed loop case the last point is equal to first.             *
  446. * Both cases returns NULL terminated list.                     *
  447. *****************************************************************************/
  448. void LoopsFromInterList(PolygonStruct *Pl,
  449.         InterSegListStruct **PClosed, InterSegListStruct **POpen)
  450. {
  451.     InterSegmentStruct *PSeg, *PSegHead, *PSegTemp, *PSegNewTemp;
  452.     InterSegListStruct *PSLTemp;
  453.  
  454. #ifdef DEBUG3
  455.     printf("Enter LoopsFromInterList\n");
  456. #endif /* DEBUG3 */
  457.  
  458.     *PClosed = (*POpen) = NULL;
  459.  
  460.     if ((PSeg = (InterSegmentStruct *) Pl -> PAux) == NULL) {
  461.     return;
  462.     }
  463.     else {
  464.     /* Do intersect - find if there are closed loops and/or open ones:   */
  465.     Pl -> PAux = NULL;
  466.     while (TRUE) {
  467.         /* First, we look for open loops - scans linearly (maybe should  */
  468.         /* be done more efficiently) for segment on boundary and start   */
  469.         /* build chain from it (up to the other end, on the boundary).   */
  470.         PSegHead = PSeg;
  471.         while (PSegHead) {
  472.         if (PSegHead -> V[0] != NULL || PSegHead -> V[1] != NULL) {
  473.             /* Found one - make it in correct order, del. from list: */
  474.             if (PSegHead -> V[0] == NULL) SwapPointInterList(PSegHead);
  475.             DeleteSegInterList(PSegHead, &PSeg);
  476.             break;
  477.         }
  478.         else
  479.             PSegHead = PSegHead -> Pnext;
  480.         }
  481.         if (PSegHead == NULL) break;    /* No more open segments here... */
  482.  
  483.         PSegTemp = PSegHead;
  484.         while (PSegTemp -> V[1] == NULL) {
  485.         /* Search for matching to the second boundary end: */
  486.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  487.         PSegTemp -> Pnext = PSegNewTemp;
  488.         PSegTemp = PSegNewTemp;
  489.         }
  490.         PSegTemp -> Pnext = NULL;
  491.         PSLTemp = (InterSegListStruct *)
  492.         MyMalloc(sizeof(InterSegListStruct), ALLOC_OTHER);
  493.         PSLTemp -> PISeg = PSegHead;
  494.         PSLTemp -> Pnext = (*POpen);
  495.         *POpen = PSLTemp;
  496.     }
  497.  
  498.     while (TRUE) {
  499.         /* Now, we look for closed loops - pick one segment and search   */
  500.         /* for matching until you close the loop.                 */
  501.         PSegHead = PSeg;
  502.         if (PSegHead == NULL) break;  /* No more closed segments here... */
  503.         DeleteSegInterList(PSegHead, &PSeg);
  504.  
  505.         PSegTemp = PSegHead;
  506.         while (!PT_EQ(PSegTemp -> PtSeg[1], PSegHead -> PtSeg[0])) {
  507.         /* Search for matching until we back at first point: */
  508.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  509.         PSegTemp -> Pnext = PSegNewTemp;
  510.         PSegTemp = PSegNewTemp;
  511.         }
  512.         PSegTemp -> Pnext = NULL;
  513.         PSLTemp = (InterSegListStruct *)
  514.         MyMalloc(sizeof(InterSegListStruct), ALLOC_OTHER);
  515.         PSLTemp -> PISeg = PSegHead;
  516.         PSLTemp -> Pnext = (*PClosed);
  517.         *PClosed = PSLTemp;
  518.     }
  519.     }
  520.  
  521. #ifdef DEBUG3
  522.     printf("Exit LoopsFromInterList\n");
  523. #endif /* DEBUG3 */
  524. }
  525.  
  526. /*****************************************************************************
  527. * Swap the two points in the InterSegmentStruct (modifies PtSeg & V entries) *
  528. *****************************************************************************/
  529. static void SwapPointInterList(InterSegmentStruct *PSeg)
  530. {
  531.     PointType Pt;
  532.     VertexStruct *V;
  533.  
  534.     PT_COPY(Pt,              PSeg -> PtSeg[0]);
  535.     PT_COPY(PSeg -> PtSeg[0], PSeg -> PtSeg[1]);
  536.     PT_COPY(PSeg -> PtSeg[1], Pt);
  537.  
  538.     V         = PSeg -> V[0];
  539.     PSeg -> V[0] = PSeg -> V[1];
  540.     PSeg -> V[1] = V;
  541. }
  542.  
  543. /*****************************************************************************
  544. * Delete one InterSegment PSeg, from InterSegmentList PSegList:             *
  545. *****************************************************************************/
  546. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  547.                         InterSegmentStruct **PSegList)
  548. {
  549.     InterSegmentStruct *PSegTemp;
  550.  
  551.     if (*PSegList == PSeg) { /* Its the first one - simply advance list ptr: */
  552.     *PSegList = (*PSegList) -> Pnext;
  553.     }
  554.     else {
  555.     PSegTemp = (*PSegList);
  556.     while (PSegTemp -> Pnext != NULL && PSegTemp -> Pnext != PSeg)
  557.         PSegTemp = PSegTemp -> Pnext;
  558.     if (PSegTemp -> Pnext == PSeg)
  559.         PSegTemp -> Pnext = PSegTemp -> Pnext -> Pnext;
  560.     else
  561.         FatalError("DeleteSegInterList: element to delete not found\n");
  562.     }
  563. }
  564.  
  565. /*****************************************************************************
  566. * Search for matching point, in the given inter segment list. Returns the    *
  567. * pointer to that element after swapping its points if needed (the match     *
  568. * must be with point 0 of new segment returned), and deleting it from list   *
  569. *****************************************************************************/
  570. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  571.                         InterSegmentStruct **PSegList)
  572. {
  573.     InterSegmentStruct *PSegTemp = (*PSegList);
  574.  
  575. #ifdef DEBUG3
  576.     printf("Enter FindMatchInterList\n");
  577. #endif /* DEBUG3 */
  578.  
  579.     while (PSegTemp != NULL) {
  580.     if (PT_EQ(Pt, PSegTemp -> PtSeg[0])) {
  581.         DeleteSegInterList(PSegTemp, PSegList);
  582.         return PSegTemp;
  583.     }
  584.     if (PT_EQ(Pt, PSegTemp -> PtSeg[1])) {
  585.         DeleteSegInterList(PSegTemp, PSegList);
  586.         SwapPointInterList(PSegTemp);
  587.         return PSegTemp;
  588.     }
  589.     PSegTemp = PSegTemp -> Pnext;
  590.     }
  591.  
  592.     FatalError("FindMatchInterList: No match found - Empty Object Result\n");
  593.     return NULL;
  594. }
  595.  
  596. /*****************************************************************************
  597. *   Sort the open loops of the given polygon to an order that can be used in *
  598. * subdividing the polygons later (see comments for ExtractPolygons).         *
  599. *   This order is such that each loops will have no other loop between its   *
  600. * end points, if we walk along the polygon in the (linked list direction)    *
  601. * perimeter from one end to the other, before it. For example:             *
  602. *             -----------------------------L3                 *
  603. *        |  ---------------L1  -----L2 |          --------L4   --L5   *
  604. *        | |               |  |     |  |         |        |   |  |    *
  605. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
  606. * In this case, any order such that L1, L2 are before L3 will do. Obviously  *
  607. * this is not a total order, and they are few correct ways to sort it.         *
  608. * Algorithm:                                     *
  609. *   For each open loop, for each of its two end, evaluate a RealType key for *
  610. * the end point P between segment P(i) .. P(i+1) to be i + t, where:         *
  611. * t is the ratio  (P - P(i)) / (P(i+1) - P(i)) . This maps the all perimeter *
  612. * of the polygon onto 0..N-1, where N is number of vertices of that polygon. *
  613. *   Sort the keys, and while they are keys in data sturcture, search and     *
  614. * remove a consecutive pair of keys assosiated with same loop, and output it *
  615. *   Note that each open loop point sequence is tested to be such that it     *
  616. * starts on the first point (first and second along vertex list) on polygon  *
  617. * perimeter, and the sequence end is on the second point, and the sequence   *
  618. * is reversed if not so. This order will make the replacement of the         *
  619. * perimeter from first to second points by the open loop much easier.         *
  620. *   This may be real problem if there are two intersection points almost     *
  621. * identical - floating point errors may cause it to loop forever. We use     *
  622. * some reordering heuristics in this case, and return fatal error if fail!   *
  623. *****************************************************************************/
  624. void SortOpenInterList(PolygonStruct *Pl, InterSegListStruct **POpen)
  625. {
  626.     int Found = TRUE, ReOrderFirst = FALSE, NumOfReOrders = 0;
  627.     RealType Key1, Key2;
  628.     InterSegmentStruct *PSeg;
  629.     InterSegListStruct *PResHead = NULL, *PResTemp, *PLSeg, *PLNext;
  630.     SortOpenStruct *PSHead = NULL, *PSTemp, *PSTemp1, *PSTemp2;
  631.  
  632. #ifdef DEBUG3
  633.     printf("Enter SortOpenInterList\n");
  634. #endif /* DEBUG3 */
  635.  
  636.     PLSeg = (*POpen);
  637.     while (PLSeg != NULL) {    /* Evaluate the two end keys and insert them: */
  638.         PSeg = PLSeg -> PISeg;
  639.     PLNext = PLSeg -> Pnext;
  640.     PLSeg -> Pnext = NULL;
  641.  
  642.     PSTemp1 = (SortOpenStruct *) MyMalloc(sizeof(SortOpenStruct),
  643.                           ALLOC_OTHER);
  644.     PSTemp1 -> PLSeg = PLSeg;
  645.     /* Insert PSTemp1 into PLHead list according to position of Pt in Pl.*/
  646.     Key1 = SortOpenInsertOne(&PSHead, PSTemp1, PSeg -> PtSeg[0],
  647.                            PSeg -> V[0], Pl);
  648.  
  649.     while (PSeg -> Pnext != NULL) PSeg = PSeg -> Pnext; /* Go other end. */
  650.     PSTemp2 = (SortOpenStruct *) MyMalloc(sizeof(SortOpenStruct),
  651.                           ALLOC_OTHER);
  652.     PSTemp2 -> PLSeg = PLSeg;
  653.     /* Insert PSTemp2 into PLHead list according to position of Pt in Pl.*/
  654.     Key2 = SortOpenInsertOne(&PSHead, PSTemp2, PSeg -> PtSeg[1],
  655.                            PSeg -> V[1], Pl);
  656.  
  657.     if (Key1 > Key2)          /* Reverse the open loop points order: */
  658.         SortOpenReverseLoop(PSTemp1);
  659.  
  660.     PLSeg = PLNext;
  661.     }
  662.  
  663.     while (PSHead != NULL) {    /* Search for consecutive pair of same loop. */
  664.     if (NumOfReOrders++ > 10)
  665.         FatalError("SortOpenInterList: fail to sort intersection list\n");
  666.     if (Found) NumOfReOrders = 0;
  667.  
  668.     Found = FALSE;
  669.     PSTemp = PSHead;
  670.     if (PSTemp -> PLSeg == PSTemp -> Pnext -> PLSeg) { /* First is pair! */
  671.         if (PResHead == NULL)
  672.         PResHead = PResTemp = PSTemp -> PLSeg;
  673.         else {
  674.         PResTemp -> Pnext = PSTemp -> PLSeg;
  675.         PResTemp = PSTemp -> PLSeg;
  676.         }
  677.         PSHead = PSHead -> Pnext -> Pnext;         /* Skip the first pair. */
  678.         MyFree((char *) PSTemp -> Pnext, ALLOC_OTHER);
  679.         MyFree((char *) PSTemp, ALLOC_OTHER);
  680.         Found = TRUE;
  681.         continue;
  682.     }
  683.     /* If we are here, first pair is not of same loop - search on: */
  684.     while (PSTemp -> Pnext -> Pnext != NULL) {
  685.         if (PSTemp -> Pnext -> PLSeg == PSTemp -> Pnext -> Pnext -> PLSeg) {
  686.         if (PResHead == NULL)
  687.             PResHead = PResTemp = PSTemp -> Pnext -> PLSeg;
  688.         else {
  689.             PResTemp -> Pnext = PSTemp -> Pnext -> PLSeg;
  690.             PResTemp = PSTemp -> Pnext -> PLSeg;
  691.         }
  692.         PSTemp2 = PSTemp -> Pnext;
  693.         PSTemp -> Pnext = PSTemp -> Pnext -> Pnext -> Pnext;
  694.         MyFree((char *) PSTemp2 -> Pnext, ALLOC_OTHER);
  695.         MyFree((char *) PSTemp2, ALLOC_OTHER);
  696.         Found = TRUE;
  697.         break;
  698.         }
  699.         PSTemp = PSTemp -> Pnext;
  700.     }
  701.     /* The only way we might found nothing is in floating point round */
  702.     /* off error - two curve ends has almost the same Key...      */
  703.     /* Note, obviously, that there are at list 4 entries in list.     */
  704.     if (!Found) {
  705.         if (!ReOrderFirst &&
  706.         APX_EQ(PSHead -> Pnext -> Key, PSHead -> Key)) {
  707.         ReOrderFirst = TRUE;
  708.         PSTemp1 = PSHead -> Pnext;
  709.         PSHead -> Pnext = PSTemp1 -> Pnext;
  710.         PSTemp1 -> Pnext = PSHead;
  711.         PSHead = PSTemp1;
  712.         continue;
  713.         }
  714.         else
  715.         ReOrderFirst = FALSE;
  716.         PSTemp = PSHead;
  717.         while (PSTemp -> Pnext -> Pnext != NULL) {
  718.         if (APX_EQ(PSTemp -> Pnext -> Key,
  719.                PSTemp -> Pnext -> Pnext -> Key)) {
  720.             PSTemp1 = PSTemp -> Pnext;
  721.             PSTemp2 = PSTemp1 -> Pnext;
  722.             PSTemp1 -> Pnext = PSTemp2 -> Pnext;
  723.             PSTemp2 -> Pnext = PSTemp1;
  724.             PSTemp -> Pnext = PSTemp2;
  725.             break;
  726.         }
  727.         PSTemp = PSTemp -> Pnext;
  728.         }
  729.     }
  730.     }
  731.  
  732.     *POpen = PResHead;
  733.  
  734. #ifdef DEBUG3
  735.     printf("Exit SortOpenInterList\n");
  736. #endif /* DEBUG3 */
  737. }
  738.  
  739. /*****************************************************************************
  740. *   Reverse the order of the open loop pointed by PSHead.             *
  741. *****************************************************************************/
  742. static void SortOpenReverseLoop(SortOpenStruct *PSHead)
  743. {
  744.     InterSegmentStruct *PINewHead = NULL, *PIHead, *PITemp;
  745.  
  746.     PIHead = PSHead -> PLSeg -> PISeg;
  747.  
  748.     while (PIHead != NULL) {
  749.     PITemp = PIHead;
  750.     PIHead = PIHead -> Pnext;
  751.     SwapPointInterList(PITemp);
  752.     PITemp -> Pnext = PINewHead;
  753.     PINewHead = PITemp;
  754.     }
  755.  
  756.     PSHead -> PLSeg -> PISeg = PINewHead;
  757. }
  758.  
  759. /*****************************************************************************
  760. *   Insert new loop PSTemp, defines key by Pt and V (V defines the vertex    *
  761. * and P is the points on it), into (decreasing) ordered list PSHead.         *
  762. *****************************************************************************/
  763. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  764.        SortOpenStruct *PSTemp, PointType Pt, VertexStruct *V, PolygonStruct *Pl)
  765. {
  766.     int i = 0;
  767.     RealType Key;
  768.     PointType Pt1, Pt2;
  769.     VertexStruct *VTemp = Pl -> V;
  770.     SortOpenStruct *PSTail;
  771.  
  772.     PSTemp -> Pnext = NULL;
  773.  
  774.     while (VTemp != V && VTemp != NULL) {
  775.     i++;
  776.     VTemp = VTemp -> Pnext;
  777.     }
  778.     if (VTemp == NULL) FatalError("SortOpenInsertOne: fail to find vertex\n");
  779.  
  780.     PT_SUB(Pt1, V -> Pnext -> Pt, V -> Pt);
  781.     PT_SUB(Pt2, Pt, V -> Pt);
  782.     Key = PSTemp -> Key = i + PT_LENGTH(Pt2) / PT_LENGTH(Pt1);
  783.  
  784.     /* Now insert PSTemp into the ordered list: */
  785.     if (*PSHead == NULL) {
  786.     *PSHead = PSTemp;
  787.     return Key;
  788.     }
  789.     if (PSTemp -> Key > (*PSHead) -> Key) {         /* Insert as first? */
  790.     PSTemp -> Pnext = (*PSHead);
  791.     *PSHead = PSTemp;
  792.     return Key;
  793.     }
  794.     PSTail = (*PSHead);
  795.     while (PSTail -> Pnext != NULL && PSTemp -> Key < PSTail -> Pnext -> Key)
  796.     PSTail = PSTail -> Pnext;
  797.     PSTemp -> Pnext = PSTail -> Pnext;
  798.     PSTail -> Pnext = PSTemp;
  799.  
  800.     return Key;
  801. }
  802.  
  803. /*****************************************************************************
  804. *   Create a new vertex list, in reverse order. The original is not modified.*
  805. *****************************************************************************/
  806. VertexStruct *GenReverseVrtxList(VertexStruct *VIn)
  807. {
  808.     VertexStruct *VOutHead, *VOut;
  809.  
  810.     VOutHead = AllocVertex(0, 0, NULL, NULL);
  811.  
  812.     PT_COPY(VOutHead -> Pt, VIn -> Pt);
  813.     VIn = VIn -> Pnext;
  814.  
  815.     while (VIn != NULL) {
  816.     VOut = AllocVertex(0, 0, NULL, NULL);
  817.     PT_COPY(VOut -> Pt, VIn -> Pt);
  818.     PT_COPY(VOut -> Normal, VIn -> Normal);
  819.  
  820.     VOut -> Pnext = VOutHead;         /* Chain them in reverse order. */
  821.     VOutHead = VOut;
  822.  
  823.     VIn = VIn -> Pnext;
  824.     }
  825.  
  826.     return VOutHead;
  827. }
  828.  
  829. #ifdef DEBUG2
  830.  
  831. /*****************************************************************************
  832. *   Print the content of the given polygon, to standard output.             *
  833. *****************************************************************************/
  834. static void PrintVrtxList(VertexStruct *V)
  835. {
  836.     VertexStruct *VHead = V;
  837.  
  838.     do {
  839.     printf("    %12lf %12lf %12lf\n", V -> Pt[0], V -> Pt[1], V -> Pt[2]);
  840.     V = V -> Pnext;
  841.     }
  842.     while (V!= NULL && V != VHead);
  843. }
  844.  
  845. /*****************************************************************************
  846. *   Print the content of the given InterSegment list, to standard output.    *
  847. *****************************************************************************/
  848. static void PrintInterList(InterSegmentStruct *PInt)
  849. {
  850.     printf("INTER SEGMENT LIST:\n");
  851.  
  852.     if (PInt) printf("Entry vertex pointer %p\n", PInt -> V[0]);
  853.     while (PInt) {
  854.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  855.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  856. #ifdef __MSDOS__
  857.         FP_SEG(PInt->V[0]),
  858. #else
  859.         PInt->V[0],
  860. #endif /* __MSDOS__ */
  861.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  862. #ifdef __MSDOS__
  863.         FP_SEG(PInt->V[1]));
  864. #else
  865.         PInt->V[1]);
  866. #endif /* __MSDOS__ */
  867.     if (PInt -> Pnext == NULL)
  868.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  869.  
  870.     PInt = PInt -> Pnext;
  871.     }
  872. }
  873.  
  874. #endif /* DEBUG2 */
  875.